package com.heima.leetcode.practice;

/**
 * @Classname E211
 * @Description leetcode 211. 添加与搜索单词 - 数据结构设计
 * @Date 2025/10/17 11:19
 * @Author 勾新杰
 */
public class E211 {

    /**
     * 字典树
     */
    static class WordDictionary {

        /**
         * 第一层的节点
         */
        private final TrieNode[] levelOne;

        /**
         * 字典树节点
         */
        static class TrieNode {

            /**
             * 当前node的孩子节点
             */
            TrieNode[] children;

            /**
             * 当前node是否是单词的结束位，有存在的必要，
             * 因为如果加了一个add单词，查找ad如果没有结束位就会返回true
             */
            boolean isEnd;

            /**
             * 构造方法
             */
            TrieNode() {
                children = new TrieNode[26];
                isEnd = false;
            }
        }

        /**
         * 构造方法
         */
        public WordDictionary() {
            levelOne = new TrieNode[26];
        }

        /**
         * 添加单词
         *
         * @param word 单词
         */
        public void addWord(String word) {
            TrieNode[] curr = levelOne;
            char[] charArray = word.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                char c = charArray[i];
                int index = c - 'a';
                if (curr[index] == null) curr[index] = new TrieNode();
                if (i == charArray.length - 1) curr[index].isEnd = true;
                curr = curr[index].children;
            }
        }

        /**
         * 查找单词，采用递归的方式
         *
         * @param word 单词
         * @return true：存在，false：不存在
         */
        public boolean search(String word) {
            return search(levelOne, word.toCharArray(), 0, word.length() - 1);
        }

        /**
         * 递归查找单词
         *
         * @param curr      当前节点
         * @param charArray 单词的字符数组
         * @param begin     单词的开始索引
         * @param end       单词的结束索引
         * @return true：存在，false：不存在
         */
        private boolean search(TrieNode[] curr, char[] charArray, int begin, int end) {
            // 1. 匹配到.
            if (charArray[begin] == '.') {
                // 1.1 循环遍历当前所有字符
                for (int i = 0; i < 26; i++) {
                    if (curr[i] == null) continue; // 为空跳过
                    if (begin == end) { // 匹配到提供的单词结束位
                        if (curr[i].isEnd) return true; // 需要判断匹配上的单词当前是否是结束位
                    } else { // 不是提供的单词的结束位，则继续递归
                        if (search(curr[i].children, charArray, begin + 1, end)) return true;
                    }
                }
                return false;
            }
            // 2. 匹配到字母
            else {
                int index = charArray[begin] - 'a';
                if (curr[index] == null) return false; // 为空则返回false
                if (begin == end) // 匹配到提供的单词结束位
                    return curr[index].isEnd; // 需要判断匹配上的单词当前是否是结束位
                else // 继续递归
                    return search(curr[index].children, charArray, begin + 1, end);
            }
        }
    }
}
